#define _CRT_SECURE_NO_WARNINGS
#include<vector>
using namespace std;
int deleteAndEarn(vector<int>& nums) {
    if (nums.size() == 1)return nums[0];

    int hash[10001] = { 0 };
    for (auto num : nums) {
        hash[num]++;
    }
    vector<int> single_nums(10001);
    int num = 0;
    for (int i = 1; i < 10001; i++) {
        if (hash[i] != 0) {
            single_nums[num++] = i;
        }
    }
    if (num == 1) {
        return single_nums[0] * hash[single_nums[0]];
    }
    vector<int> dp(num);
    dp[0] = single_nums[0] * hash[single_nums[0]];
    if (single_nums[0] + 1 == single_nums[1]) {
        if (single_nums[1] * hash[single_nums[1]] > dp[0]) {
            dp[1] = single_nums[1] * hash[single_nums[1]];
        }
        else {
            dp[1] = dp[0];
        }
    }
    else {
        dp[1] = dp[0] + single_nums[1] * hash[single_nums[1]];
    }

    for (int i = 2; i < num; i++) {
        if (single_nums[i - 1] + 1 == single_nums[i]) {
            dp[i] = max(single_nums[i] * hash[single_nums[i]] + dp[i - 2], dp[i - 1]);
        }
        else {
            dp[i] = dp[i - 1] + single_nums[i] * hash[single_nums[i]];
        }
    }
    return dp[num - 1];
}

int main() {
    vector<int> v = { 8,3,4,7,6,6,9,2,5,8,2,4,9,5,9,1,5,7,1,4 };
    int ret = deleteAndEarn(v);

    return 0;
}